{ "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "name": "Arcadia deliveries.ipynb", "provenance": [], "authorship_tag": "ABX9TyMBjD2eZdN3iXnRzoSpqrlU", "include_colab_link": true }, "kernelspec": { "name": "python3", "display_name": "Python 3" }, "language_info": { "name": "python" }, "pycharm": { "stem_cell": { "cell_type": "raw", "source": [], "metadata": { "collapsed": false } } } }, "cells": [ { "cell_type": "markdown", "source": [ "# Arcadia deliveries\n", "## Try me\n", "\n", " [![Open In Colab](../../_static/colabs_badge.png)](https://colab.research.google.com/github/ffraile/operations-research-notebooks/blob/main/docs/source/MIP/solved/Arcadia_deliveries%20(Solved).ipynb)[![Binder](../../_static/binder_badge.png)](https://mybinder.org/v2/gh/ffraile/operations-research-notebooks/main?labpath=docs%2Fsource%2FMIP%2Fsolved%2FArcadia_deliveries%20(Solved).ipynb)\n", "\n", "## Problem definition\n", "Arcadia Deliveries wants to determine the best location for their warehouses to supply the different retail regions of their best customer.\n", "There are 5 possible warehouse locations and 10 different retail regions.\n", "The following table shows the capacity and operation costs of the possible warehouse locations:\n", "\n", "| Data | warehouse 1 | warehouse 2 | warehouse 3 | warehouse 4 | warehouse 5 |\n", "| --------------- | ----------- | ----------- | ----------- | ----------- | ----------- |\n", "| capacity | 1000 | 2000 | 3000 | 4000 | 5000 |\n", "| Operation costs | 50 | 60 | 70 | 80 | 90 |\n", "\n", "The following table contains the demand at each region:\n", "\n", "| Region | Demand |\n", "| -------- | ------ |\n", "| Region 1 | 100 |\n", "| Region 2 | 200 |\n", "| Region 3 | 300 |\n", "| Region 4 | 400 |\n", "| Region 5 | 500 |\n", "| Region 6 | 600 |\n", "| Region 7 | 700 |\n", "| Region 8 | 800 |\n", "| Region 9 | 900 |\n", "| Region 10 | 1000 |\n", "\n", "\n", "And the following cost contains the transportation costs from warehouses to regions:\n", "\n", "| Region | Warehouse 1 | Warehouse 2 | Warehouse 3 | Warehouse 4 | Warehouse 5 |\n", "| ------ | ----------- | ----------- | ----------- | ----------- | ----------- |\n", "| 1 | 42 | 36 | 58 | 47 | 32 |\n", "| 2 | 73 | 56 | 73 | 78 | 38 |\n", "| 3 | 38 | 41 | 80 | 88 | 69 |\n", "| 4 | 59 | 70 | 77 | 94 | 51 |\n", "| 5 | 51 | 92 | 79 | 88 | 80 |\n", "| 6 | 38 | 98 | 57 | 64 | 96 |\n", "| 7 | 86 | 53 | 86 | 58 | 44 |\n", "| 8 | 48 | 92 | 40 | 100 | 71 |\n", "| 9 | 62 | 60 | 30 | 31 | 63 |\n", "| 10 | 43 | 43 | 48 | 63 | 55 |\n", "\n", "Find the optimal location for warehouses and determine which warehouses are going to deliver to every retail location, knowing that the customer requires that a region is supplied from only one source\n", "\n" ], "metadata": { "id": "IvMfG6hMKOIa" } }, { "cell_type": "markdown", "metadata": { "id": "VIEijyfdKNIX" }, "source": [ "## Problem model\n", "This is a transportation problem with a single-source facility constraint, where the sources are the sourcing warehouses \n", "and the destination the retail regions. \n", "\n", "The objective is to minimize the transportation costs, taking into account transportation costs and the operation costs. \n", "\n", "**Indices**\n", "Let us define the following indices:\n", " \n", "- $i$: warehouse location ($i \\in [1, ..., 5]$)\n", "\n", "- $j$: retail region ($j \\in [1, ..., 10]$)\n", "\n", "\n", "**Data**\n", "Looking at the data, we can define the following vector containing the operation costs: \n", "\n", "$f = [f_1, f_2, ..., f_5] = [50, 60, 70, 80, 90]$\n", "\n", "and the following matrix containing the transportation costs from every warehouse to every retail region:\n", "\n", "$C = \n", "\\begin{bmatrix}\n", "c_{11} & c_{12} & ... & c_{15}\\\\\n", "c_{21} & c_{22} & ... & c_{25}\\\\\n", "... \\\\\n", "c_{101} & c_{102} & ... & c_{105}\\\\\n", "\\end{bmatrix}$ \n", "\n", "Or, using the values given in the table above:\n", "\n", "$C^T = \n", "\\begin{bmatrix}\n", "42 & 36 & 58 & 47 & 32\\\\\n", "73 & 56 & 73 & 78 & 38\\\\\n", "38 & 41 & 80 & 88 & 69\\\\\n", "59 & 70 & 77 & 94 & 51\\\\\n", "51 & 92 & 79 & 88 & 80\\\\\n", "38 & 98 & 57 & 64 & 96\\\\\n", "86 & 53 & 86 & 58 & 44\\\\\n", "48 & 92 & 40 & 100 & 71\\\\\n", "62 & 60 & 30 & 31 & 63\\\\\n", "43 & 43 & 48 & 63 & 55\\\\\n", "\\end{bmatrix}$\n", "\n", "Besides the costs, each warehouse has a limited sourcing capacity, which can be identified as a vector:\n", "\n", "$s = [s_1, s_2, ..., s_5] = [1000, 2000, 3000, 4000, 5000]$\n", "\n", "And the following vector contains the demand for every region: \n", "\n", "$d = [d_1, d_2, ..., d_{10}] = [100, 200, 300, 400, 500, 600, 700, 800, 900, 1000]$\n", "\n", "Let us define the following decision variables: \n", "\n", "- $X_{ij}$: (Binary) determines if warehouse $i$ delivers all demand to retail region $j$ {1 if yes, 0 otherwise}\n", "- $Y_{i}$: (Binary) determines if warehouse $i$ delivers to any retail region {1 if yes, 0 otherwise}\n", "\n", "**Objective function** \n", "The objective function is: \n", "\n", "$\\min z = \\sum_{i=1}^5{\\sum_{j=1}^{10}{c_{ij}*d_j*X_{ij}}} + \\sum_{i=1}^5{Y_i*f_i}$\n", "\n", "**Constraints**\n", "The constraints are:\n", "\n", "**Sourcing capacity**:\n", " \n", "$\\sum_{j=1}^m{d_j*X_{ij}} \\leq s_i*Y_i \\quad \\forall i$ \n", "\n", "These five constraints represent the limited capacity of the warehouses, we multiply the capacity with the corresponding \n", "$Y_{i}$ variable to make sure the solution is logical and that the right-hand-side is zero if $Y_{i}$ is zero. \n", "\n", "**Demand**\n", "\n", "$\\sum_{i=1}^n{X_{ij}} = 1 \\quad \\forall j$ \n", "\n", "Since we source all the demand from a single source, we only need to make sure that the demand is supplied from 1 \n", "location for every warehouse. " ] }, { "cell_type": "markdown", "source": [ "## Implementation in Python\n", "### Requirements\n", "Install the following requirements to run this cell:" ], "metadata": { "collapsed": false } }, { "cell_type": "code", "execution_count": null, "outputs": [], "source": [ "!pip install pandas\n", "!pip install pulp\n", "!pip install IPython" ], "metadata": { "collapsed": false, "pycharm": { "is_executing": true } } }, { "cell_type": "markdown", "source": [ "### Implementation" ], "metadata": { "collapsed": false } }, { "cell_type": "code", "execution_count": 6, "outputs": [ { "name": "stdout", "text": [ "Optimal\n" ], "output_type": "stream" }, { "data": { "text/plain": "", "text/markdown": "Total cost is **235370.00 €**" }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": "", "text/markdown": "##Decision Variables##" }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": "", "text/markdown": "The following table displays the values of the decision variables $X_{ij}$. The orientation is the same as in the table that provided the data in the first place" }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": " 1 2 3 4 5\n1 0 0 0 0 1\n2 0 0 0 0 1\n3 1 0 0 0 0\n4 0 0 0 0 1\n5 1 0 0 0 0\n6 0 0 1 0 0\n7 0 0 0 0 1\n8 0 0 1 0 0\n9 0 0 1 0 0\n10 0 1 0 0 0", "text/html": "
\n\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n
12345
100001
200001
310000
400001
510000
600100
700001
800100
900100
1001000
\n
" }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": "", "text/markdown": "And the following table displays the values of the decision variables $Y_i$" }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": " 1 2 3 4 5\nY 1 1 1 0 1", "text/html": "
\n\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n
12345
Y11101
\n
" }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": "", "text/markdown": "Note that $Y_i$ is only 1 if the warehouse is used to deliver to any region" }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Import libraries\n", "import pandas as pd\n", "import pulp\n", "import numpy as np\n", "from IPython.display import display, Markdown\n", "\n", "# Instantiate our problem class\n", "\n", "\n", "model = pulp.LpProblem(\"Minimise_transportation_costs\", pulp.LpMinimize)\n", "\n", "# Define decision variables\n", "\n", "# Construct our decision variable lists\n", "warehouse = [1, 2, 3, 4, 5]\n", "region = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]\n", "\n", "\n", "X = pulp.LpVariable.dicts(\"X_\",\n", " ((i, j) for i in warehouse for j in region),\n", " lowBound=0,\n", " cat='Binary')\n", "\n", "Y = pulp.LpVariable.dicts(\"Y_\", (i for i in warehouse),\n", " lowBound=0,\n", " cat='Binary')\n", "\n", "# Data\n", "transportation_costs = np.array([[42, 73, 38, 59, 51, 38, 86, 48, 62, 43], [36, 56, 41, 70, 92, 98, 53, 92, 60, 43], [58, 73, 80, 77, 79, 57, 86, 40, 30, 48], [47, 78, 88, 94, 88, 64, 58, 100, 31, 63], [32, 38, 69, 51, 80, 96, 44, 71, 63, 55]])\n", "\n", "operation_costs = np.array([50, 60, 70, 80, 90])\n", "\n", "capacity = np.array([1000, 2000, 3000, 4000, 5000])\n", "\n", "demand = np.array([100, 200, 300, 400, 500, 600, 700, 800, 900, 1000])\n", "\n", "model += pulp.lpSum([demand[j]*transportation_costs[i,j]*X[(warehouse[i],region[j])] for i in range(len(warehouse)) for j in range(len(region))]) + pulp.lpSum([operation_costs[i]*Y[warehouse[i]] for i in range(len(warehouse))])\n", "\n", "# Capacity constraints\n", "for i in range(len(warehouse)):\n", " model += pulp.lpSum([demand[j]*X[(warehouse[i],region[j])] for j in range(len(region))]) <= capacity[i]*Y[warehouse[i]], \"source_capacity_\" + str(i) \n", "\n", "# Demand constraints\n", "for j in range(len(region)):\n", " model += pulp.lpSum([demand[j]*X[(warehouse[i],region[j])] for i in range(len(warehouse))]) >= demand[j], \"demand_region_\" + str(j)\n", "\n", "model.solve()\n", "print(pulp.LpStatus[model.status])\n", "\n", "total_cost = pulp.value(model.objective)\n", "display(Markdown(\"Total cost is **%0.2f €**\"%total_cost))\n", "\n", "#Let us now show the solution as pandas dataframes \n", "x_df = pd.DataFrame(columns=warehouse)\n", "\n", "display(Markdown(\"##Decision Variables##\"))\n", "display(Markdown(\"The following table displays the values of the decision variables $X_{ij}$. The orientation is the same as in the table that provided the data in the first place\"))\n", "for j in range(len(region)):\n", " row_name = region[j]\n", " row_values = {}\n", " for i in range(len(warehouse)):\n", " row_values[warehouse[i]]=int(X[(warehouse[i],region[j])].value())\n", "\n", " row_series = pd.Series(row_values, name=row_name)\n", " x_df = x_df.append(row_series)\n", " \n", "display(x_df)\n", "\n", "y_df = pd.DataFrame(columns=warehouse)\n", "y_values = {}\n", "for i in range(len(warehouse)):\n", " y_values[warehouse[i]]=int(Y[(warehouse[i])].value())\n", "\n", "y_df = y_df.append(pd.Series(y_values, name=\"Y\"))\n", "\n", "display(Markdown(\"And the following table displays the values of the decision variables $Y_i$\"))\n", "display(y_df)\n", "display(Markdown(\"Note that $Y_i$ is only 1 if the warehouse is used to deliver to any region\"))\n" ], "metadata": { "collapsed": false, "pycharm": { "is_executing": false } } } ] }